#include "graph.h"
#include <_stdlib.h>
#include <bits/stdc++.h>
#include <queue>
#include <deque>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int,int> pii;
int deg[N];
vector<int> edg[N];
int tim = 0;
int top = 0;
pair<pair<int,int> ,int> stk[N];
vector<int> tpos;
mt19937 rnd(time(0));
int col[N];
int ncol[N];
vector<pair<pair<int,int>,vector<int> > > regions;
vector<pair<pair<int,int>,vector<int> > > tmp;
// int sum = 0;
void solve(int u){
    // cout << "\tSOLVING:" << u << "\n";
    regions.clear();
    tmp.clear();
    regions.push_back(make_pair(make_pair(1,top),tpos));
    for(int i = 1 ; i <= (1 + top) / 2; ++i )ncol[i] = 1;
    for(int i = (1 + top) / 2 + 1; i <= top ; ++ i)ncol[i] = 2;
    // cout << top << " " << tpos.size() << "\n";
    // sum += top + tpos.size();
    // cout << sum << "\n";
    // for(int i = top ; i ; -- i){
    //     cout << stk[i].second << " " << stk[i].first.first << " " << stk[i].first.second << "\n";
    // }
    for(int i = top ; i >= 2; -- i){
        Move(stk[i].first.first,ncol[i]);
    }
    // cout << "OK1"
    for(int i = 2 ; i <= top; ++ i){
        Move(stk[i].first.second,ncol[i-1]);
    }
    // for(int i = 2; i <= top ; ++ i){
        // cout << ncol[i] << " ";
    // }
    // cout << "\n";
    for(int i = 0; i < regions.size(); ++ i){
        for(int x : regions[i].second){
            Move(x,Color());
            col[x] = Color();
            Move(LastRoad(),col[x]);
        }
    }
    for(int i = 1; i <= 10; ++ i){
        if(regions.empty())break;
        for(int j = 0; j < regions.size(); ++ j){
            if(regions[j].second.empty())continue;
            pii len = regions[j].first;
            // cout << "RNG: " << len.first << "," << len.second << "\n";
            if(len.second == len.first){
                // cout << len.first << " " << stk[len.first].second << "\n";
                int v = stk[len.first].second;
                edg[u].push_back(v);
                edg[v].push_back(u);
            }else{
                bool ok1 = 0, ok2 = 0;
                vector<int> n1,n2;
                for(int x : regions[j].second){
                    if(col[x] == 1)ok1 = 1,n1.push_back(x);
                    else if(col[x] == 2)ok2 = 1,n2.push_back(x);
                }
                int mid = (len.first + len.second) >> 1;
                if(ok1)tmp.push_back(make_pair(make_pair(len.first,mid),n1));
                if(ok2)tmp.push_back((make_pair(make_pair(mid+1,len.second),n2)));
            }
        }
        // cout << "\n";
        regions.clear();
        regions = tmp;
        tmp.clear();
        for(int j = 0; j < regions.size(); ++ j){
            pii len = regions[j].first;
            int l = len.first ,r = len.second;
            int mid = (l + r ) >> 1;
            for(int i = l ; i <= mid; ++ i)ncol[i] = 1;
            for(int i = mid+1; i <= r ; ++ i)ncol[i] = 2;
        }
        for(int i = top ; i >= 2; -- i){
            Move(stk[i].first.first,ncol[i]);
        }
        for(int i = 2 ; i <= top; ++ i){
            Move(stk[i].first.second,ncol[i-1]);
        }
        for(int i = 0; i < regions.size(); ++ i){
            for(int x : regions[i].second){
                Move(x,Color());
                col[x] = Color();
                Move(LastRoad(),col[x]);
            }
        }
        // for(int i = 1; i <= top ; ++ i){
        //     cout << ncol[i] << " ";
        // }
        // cout << "\n";
    }
    for(int i = top ; i >= 2; -- i){
        Move(stk[i].first.first,2);
    }
    for(int i = 2 ; i <= top; ++ i){
        Move(stk[i].first.second,2);
    }
}
void dfs(int u,int to){
    int fa = LastRoad();
    stk[++top] = make_pair(make_pair(fa,to),u);
    deg[u] = NumberOfRoads();
    int p[202];
    for(int i = 1; i <= deg[u] ; ++ i)p[i] = i;
    shuffle(p+1,p+deg[u]+1,rnd);
    vector<int> pos;
    for(int i = 1; i <= deg[u]; ++ i){
        int v = p[i];
        if(v == fa)continue;
        Move(v,2);
        int c = Color();
        if(c != 1){
            Move(LastRoad(),c);
            pos.push_back(v);
        }else{
            edg[u].push_back(++tim);
            edg[tim].push_back(u);
            dfs(tim,v);
        }
    }
    tpos.clear();
    for(int v : pos){
        Move(v,2);
        int c = Color();
        if(c == 2)tpos.push_back(v);
        Move(LastRoad(),c);
    }
    if(tpos.size()){
        solve(u);
    }
    tpos.clear();
    --top;
    if(fa!=-1)Move(fa,3);
}
int dis[300][300];
bool vis[300];
int ans[300];
void bfs(int u){
    for(int i = 1; i <= tim ; ++ i) vis[i] = 0;
    vis[u] = 1;
    queue<pii> q;
    q.push(make_pair(u,0));
    dis[u][u] = 0;
    while(!q.empty()){
        int v = q.front().first,dist = q.front().second;q.pop();
        dis[u][v] = dist;
        for(int x : edg[v]){
            if(vis[x])continue;
            vis[x] = 1;
            q.push(make_pair(x,dist+1));
        }
    }
}
void work(){
    tim = 0;
    dfs(++tim,0);
    // cout << "TIM:" << tim << "\n";
    // for(int i = 1; i <= tim ; ++ i){
    //     cout << i << "->";
    //     for(int v : edg[i])cout << v << ",";
    //     cout << "\n";
    // }
    for(int i = 1; i <= tim; ++ i)bfs(i);
    for(int i = 1; i <= tim; ++ i){
        for(int j = i+1; j <= tim ; ++ j){
            ans[dis[i][j]]++;
        }
    }
    // for(int i = 1; i <= tim ; ++ i)cout << ans[i] << " ";
    // cout << "\n";
}
void Inspect(int R) {
    work();
    for(int i = 1; i <= R; ++ i)Answer(i,ans[i]);
}
